package com.rr.middle;

import java.util.Set;
import java.util.TreeSet;

/**
 * https://leetcode.cn/problems/number-of-times-binary-string-is-prefix-aligned/
 * 找前缀一致
 */
public class NumTimesAllBlue {
    public int numTimesAllBlue(int[] flips) {
        int firstOne = Integer.MAX_VALUE;
        int lastOne = Integer.MIN_VALUE;
        int firstZero = 0;
        int ans = 0;
        Set<Integer> onePositionSet = new TreeSet<>();
        for (int flip : flips) {
            onePositionSet.add(flip - 1);
            firstOne = Math.min(firstOne, flip - 1);
            lastOne = Math.max(lastOne, flip - 1);
            while (onePositionSet.contains(firstZero)) {
                firstZero++;
            }
            if (firstOne == 0 && firstZero > lastOne) {
                ans++;
            }
        }
        return ans;
    }


    public static void main(String[] args) {
        int[] ints = new int[]{4,1,2,3};
        System.out.println(new NumTimesAllBlue().numTimesAllBlue(ints));
    }
}
